package com.qch.edu.sort.gaojiSort;

/**
 * @Author qch
 * @Date 2021/3/6
 *
 *快速排序：不稳，O(nlog^n),最差（O(n^2)）,空间O(log^N)
 *
 * 双边循环法：选一个数作为基准数，和首位交换位置，然后与基准数比较
 *             大于基准，右指针左移小于等于基准，左指针右移
 *
 * 双轴快排思想(Arrays.sort())：选两个数为轴分区分成三个区less.mid.more->
 * Arrays.sort()<286 单轴
 * 思想：以某一位置为轴，左边是比轴小的，右边是比轴大的（递归）
 * 小区扩展，第一个数和轴数进行比较，若果小，分区扩展，如果大，和轴数前面的数进行位置替换，再讲其与轴进行比较
 * 直到比轴小的数都找到，把轴和分区的后一个位置进行替换（或者大区小区一期扩展）
 * 常用思想：两端一期，找到第一个比中轴小和比中轴大的数直接做交换
 */
public class QuickSort {
    public static void main(String[] args) {
       // int[] arr={10,9,2,4,5,1,3,8,6,55};
        int[] arr={10,9,2,4,5,1,3,8,6,55,6,6};
        //int[] arr={4,9};
        sort(arr,0,arr.length-1);
        print(arr);
    }
    static void sort(int[] arr,int leftBound,int rightBound)
    {
        if(leftBound>=rightBound)return;
        int mid = partition(arr, leftBound, rightBound);
        sort(arr,leftBound,mid-1);
        sort(arr,mid+1,rightBound);
    }
    static int partition (int[] arr,int leftBound,int rightBound)
    {
        int pivot=arr[rightBound];//轴内容
        int left=leftBound;
        int right=rightBound-1;
        while (left<=right)
        {
            //极端情况最后一个数就是最大,或者最小
            while (left<=right&&arr[left] <= pivot) left++;

            while (left<=right&&arr[right] >pivot) right--;
            System.out.println("left=>"+arr[left]+"right=>"+arr[right]);
            if(left<right)
                swap(arr,left,right);
        }
        swap(arr,left,rightBound);
        return left;
    }
    static void swap(int[] arr,int i,int j)
    {
        int temp=arr[i];
        arr[i]=arr[j];
        arr[j]=temp;
    }
    static void print(int[] arr){
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]+",");
        }
    }
}
